package com.chj.zhongji.class01;

import java.util.ArrayDeque;
import java.util.Deque;

// https://blog.csdn.net/weixin_44726516/article/details/111566659
// https://www.nowcoder.com/questionTerminal/ed610b2fea854791b7827e3111431056?toCommentId=4141697
// https://codeleading.com/article/61172121039/
public class Code05_MaxRectangle2 {
	public static int maxRecSize(int[][] map) {
		if (map == null || map.length == 0 || map[0].length == 0) {
			return 0;
		}
		int maxArea = 0;
		// 创建数组，来存储高度
		int[] height = new int[map[0].length];
		/**
		 * 第一个for循环是进行切割工作 第二个for循环是对第j列位置往上1的数量，即是高度
		 */
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
			}
			maxArea = Math.max(maxRecFromBottom(height), maxArea);
		}
		return maxArea;
	}

	/**
	 * 计算在当前行为基础的情况下，最大的矩形是什么。 在其中使用到了单调栈的思想。
	 */
	public static int maxRecFromBottom(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}
		int maxArea = 0;
		// 单调栈
		Deque<Deque<Integer>> stack = new ArrayDeque<>();
		for (int i = 0; i < height.length; i++) {
			while (!stack.isEmpty() && height[i] <= height[stack.peek().getFirst()]) {
				Deque<Integer> popQueue = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().getLast();
				while (!popQueue.isEmpty()) {
					int popIndex = popQueue.pollLast();
					int curArea = (i - leftLessIndex - 1) * height[popIndex];
					maxArea = Math.max(maxArea, curArea);
				}
			}

			if (!stack.isEmpty() && height[i] == height[stack.peek().getFirst()]) {
				stack.peek().addLast(Integer.valueOf(i));
			} else {
				Deque<Integer> pq = new ArrayDeque<>();
				pq.addLast(Integer.valueOf(i));
				stack.push(pq);
			}
		}
		// 遍历结束，stack中仍有剩余元素未经扩展。需要将其依次弹出，并进行计算
		while (!stack.isEmpty()) {
			Deque<Integer> popNodes = stack.pop();
			int leftIndex = stack.isEmpty() ? -1 : stack.peek().getLast();
			while (!popNodes.isEmpty()) {
				int popIndex = popNodes.pollLast();
				int curArea = (height.length - leftIndex - 1) * height[popIndex];
				maxArea = Math.max(maxArea, curArea);
			}
		}

		return maxArea;
	}

	public static void main(String[] args) {
		int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
		System.out.println(maxRecSize(map));
	}
}
